Équation diophantienne et divisions euclidiennes - Corrigé

Énoncé

1. Résoudre l'équation \((E) \colon 29x-11y=8\) dans \(\mathbb{Z}^2\) .

2. Déterminer tous les entiers naturels \(N\) inférieurs à \(1\,000\) tels que, dans la division euclidienne de \(N\) par \(29\) , le reste soit \(2\) , et dans celle de \(N\) par \(11\) , le reste soit \(10\) .

Solution

1.

• On applique l'algorithme d'Euclide pour \(29\) et \(11\) :
  \(\begin{align*}\renewcommand{\arraystretch}{1.2}\begin{array}{|c|c|c|c|}\hline a&b&q&r \\ \hline 29&11&2&7\\ \hline 11&7&1&4\\ \hline 7&4&1&3\\ \hline 4&3&1&1\\ \hline 3&1&3&0\\ \hline \end{array} \begin{array}{l}\ \\ \times (-3) \\ \times 2 \\ \times (-1) \\ \times 1 \\ \ \end{array}\end{align*}\)  
  On a donc \(\mathrm{PGCD}(29;-11)=\mathrm{PGCD}(29;11)=1\) , et comme \(1\) divise \(8\) , l'équation \((E)\) admet des solutions.
  
• En additionnant les lignes après avoir éliminé les restes intermédiaires, on obtient :
  \(\begin{align*}29 \times (-3)+11 \times 2=11 \times 2 \times (-3)+1& \ \ \Longleftrightarrow \ \ 29 \times (-3)+11 \times 8=1\\ & \ \ \Longleftrightarrow \ \ 29 \times (-3)-11 \times (-8)=1 \\ & \ \ \Longleftrightarrow \ \ 29 \times (-24)-11 \times (-64)=8 \end{align*}\)  donc \((x_0;y_0)=(-24;-64)\) est une solution particulière de \((E)\) .
  
• Soit \((x;y)\) une solution de \((E)\) .
  On a  \(\begin{align*}29x-11y=29 \times (-24)-11 \times (-64)& \ \ \Longleftrightarrow \ \ 29(x+24)=11(y+64)\end{align*}\) . 
  On en déduit que \(29\) divise \(11(y+64)\) .
  Or \(\mathrm{PGCD}(29;11)=1\) , donc d'après le théorème de Gauss, \(29\) divise \(y+64\) , c'est-à-dire qu'il existe \(k \in \mathbb{Z}\) tel que  \(\begin{align*}y+64=29k \ \ \Longleftrightarrow \ \ y=29k-64\end{align*}\) .
  On a alors
  \(\begin{align*}29(x+24)=11(y+64)& \ \ \Longleftrightarrow \ \ 29(x+24)=11\times 29k\\& \ \ \Longleftrightarrow \ \ x+24=11k\\& \ \ \Longleftrightarrow \ \ x=11k-24.\end{align*}\)    
  Ainsi, les solutions de \((E)\) sont des couples de la forme \((x;y)=(11k-24;29k-64)\) avec \(k \in \mathbb{Z}\) .
  
• Réciproquement, soit \(k \in \mathbb{Z}\) quelconque et \((x;y)=(11k-24;29k-64)\) .
  On a  \(\begin{align*}29x-11y& = 29(11k-24)-11(29k-64)= 29 \times (-24)-11 \times (-64)=8\end{align*}\) donc \((x;y)\) est solution de \((E)\) .
  
• En conclusion, les solutions de \((E)\) sont données par \(S=\left\lbrace(11k-24;29k-64) \colon k \in \mathbb{Z} \right\rbrace\) .
  

2. Soit \(N \in \mathbb{N}\) inférieur à \(1000\) tel que \(N=29x+2=11y+10\) avec \(x\) , \(y \in \mathbb{Z}\) . On en déduit que  \(\begin{align*}29x+2=11y+10& \ \ \Longleftrightarrow \ \ 29x-11y=8\end{align*}\) et donc, d'après la question précédente, il existe \(k \in \mathbb{Z}\) tel que \((x;y)=(11k-24;29k-64)\) .

On a alors  \(\begin{align*}N=29x+2=29(11k-24)+2=319k-694\end{align*}\) . 

Or \(N\) est un entier naturel inférieur à \(1\,000\) , donc 
\(\begin{align*}0 \leqslant N \leqslant 1\,000& \ \ \Longleftrightarrow \ \ 0 \leqslant 319k-694 \leqslant 1\,000\\ & \ \ \Longleftrightarrow \ \ 694 \leqslant 319k \leqslant 1\,694\\ & \ \ \Longleftrightarrow \ \ \frac{694}{319} \leqslant k \leqslant \frac{1\,694}{319}\\ & \ \ \Longleftrightarrow \ \ 3 \leqslant k \leqslant 5\end{align*}\)   

car \(k \in \mathbb{Z}\) , \(\dfrac{694}{319}\approx 2,2\) et \(\dfrac{1\,694}{319} \approx 5,3\) .

Il y a donc trois valeurs possibles pour \(N\) :

• si \(k=3\) : \(N=319 \times 3-694=263\) ;
• si \(k=4\) : \(N=319 \times 4-694=582\) ;
• si \(k=5\) : \(N=319 \times 5-694=901\) .